#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
using namespace std;
const int N = 100010;
int n, m;

struct edge {
	int v, w;
};

vector<edge> e[N];
int d[N], vis[N];

priority_queue<pair<int, int>> q;

void dijkstra() {
	for (int i = 0; i <= n; i++) d[i] = 1e9;
	d[1] = 0; q.push({ 0,1 });
	while (q.size()) {
		auto t = q.top(); q.pop();
		int u = t.second;
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto ed : e[u]) {
			int v = ed.v, w = ed.w;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				q.push({ -d[v],v });
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		e[a].push_back({ b,c });
	}
	dijkstra();
	return 0;
}